package com.clei.algorithm.other;

import com.clei.utils.PrintUtil;

/**
 * 四皇后
 *
 * @author Y
 * @date 2023-01-20
 */
public class Queen {

    public static void main(String[] args) {
        int number = 4;
        int[] res = new int[number];
        for (int i = 0; i < number; i++) {
            res[i] = -1;
        }
        find(number, 0, res);
    }

    /**
     * 找结果
     *
     * @param number number
     * @param i      i
     * @param res    res
     */
    private static void find(int number, int i, int[] res) {
        if (i == number) {
            // 找到解
            if (res[number - 1] != -1) {
                print(4, res);
            }
            return;
        }
        for (int j = 0; j < number; j++) {
            // 当前位置是否合适
            if (ok(i, j, res)) {
                res[i] = j;
                // 下个位置
                find(number, i + 1, res);
                // 回溯
                res[i] = -1;
            }
        }
    }

    /**
     * 当前位置是否合适
     *
     * @param i   i
     * @param j   j
     * @param res res
     * @return true or false
     */
    private static boolean ok(int i, int j, int[] res) {
        for (int k = 0; k < i; k++) {
            if (res[k] == j || i - k == Math.abs(j - res[k])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印
     *
     * @param number number
     * @param res    结果
     */
    private static void print(int number, int[] res) {
        for (int i = 0; i < number; i++) {
            for (int j = 0; j < number; j++) {
                PrintUtil.print(j == res[i] ? 1 : 0);
            }
            PrintUtil.println();
        }
        PrintUtil.println();
    }
}
